最新研究：只需1.3万个量子比特，即可破解2048位RSA加密

光子盒研究院出品

早在2019年，谷歌团队宣布，量子计算机将在8小时内破解2048位RSA加密，但是需要2000万个量子比特。这样规模的量子计算机显然是一个遥不可及的梦想。最近在一项新的工作中，法国新能源与原子能委员会的Élie Gouzien和Nicolas Sangouard证明，通过将量子存储器集成到量子计算机中，13436个量子比特就能破解RSA-2048，比此前研究中所需的量子比特数减少了3个数量级。

9月28日，相关论文发表在《物理评论快报》上[1]。

这项研究表明，破解当前主流的2048位RSA加密，在可预见的未来就可能实现，因为根据IBM和谷歌的技术路线图，到2029年将实现百万量子比特。尽管估计1.3万个量子比特的破解时间长达177天，但未来随着量子比特数的增加，所需时间将指数级缩减。量子计算机对当前公钥基础设施的威胁已经越来越近。

几十年来，全球通信加密几乎都依赖于公钥基础设施，其中最重要的公钥加密体制之一就是RSA加密算法。它基于一个简单的数论事实：将两个质数相乘较为容易，反过来，将其乘积进行因式分解而找到构成它的质数却非常困难。

例如，计算17×37=629是很容易的，但是如果反过来，给你629，要你找出它的因子就困难多了。并且，正向计算与逆向计算难度的差异随着数值的增大而急剧增大。

随着算力不断提升，RSA的位数也越来越长，目前典型密钥长度是2048位，如果试图使用经典计算机破解RSA-2048，时间将无法估计。但量子计算机就是为此而生的，1994年提出的Shor算法理论上可以实现因式分解的指数级加速，早期人们对于构建量子计算机的兴趣正源于此。

2001年，7量子比特NMR量子计算机首次演示了Shor算法，将15分解为5和3，证明了Shor算法的可行性。

但当前量子计算机的能力对于长度在几千位的RSA密钥没有任何威胁。2015年，研究人员估计[2]，量子计算机需要十亿个量子比特才能破解RSA-2048。而像IBM、谷歌这样的量子计算领先公司至今还没有跨入100量子比特的门槛。

2019年，谷歌团队的论文[3]称，量子计算机在8小时内就能破解2048位RSA加密，但是需要2000万个量子比特。相比10亿个量子比特，谷歌团队大大减少了运行算法所需的资源，但是一台2000万量子比特的量子计算机显然是一个遥不可及的梦想。

在谷歌的研究中，他们提出的是标准的超导量子比特计算机架构，其处理器由2D量子比特网格组成，需要大量的量子比特。而在法国团队的研究中，Gouzien和Sangouard将2D量子比特网格连接到一个3D结构的量子存储器。

他们设想一个可以存储多个空间横向模式和时间模式的量子存储器。存储器可以视为是一个量子比特寄存器，其中每个量子比特的地址由时间和空间索引标识。当一个给定的量子比特需要处理时，它的状态被释放，并通过微波场以对应于量子比特地址的时间和空间模式映射到处理器中。当处理完成时，量子比特状态被映射回存储器并被存储，直到需要另一个处理操作。

更准确地说，研究人员使用3D纠错码，其中每个逻辑量子比特的地址被编码到物理地址的3D结构中，两个维度在空间中编码，一个维度在时间中编码(如图1)。通过顺序释放对应于不同“水平”切片(具有不同的时间索引)的物理量子比特并同时处理每个切片(具有相同的时间索引)，应用纠错和逻辑门。

图1 量子计算机架构，使用由2D量子比特网格构成的处理器和作为量子比特寄存器运行的存储器，其中每个量子比特的地址由时间和空间索引指定。仅表示逻辑量子比特；附加的辅助量子比特用于测量用于纠错的算符

他们提出了一种利用微波接口实现这种架构的方法，这种微波接口是由超导量子比特制成的处理器和利用嵌入空腔的稀土离子掺杂固体中光子回波原理的多路复用存储器之间的接口。

为了将这种架构与标准架构进行比较，他们估计了破解RSA所需的资源。研究表明，这种带有量子存储器的量子计算机设计，只需要13436个物理量子比特就可以分解2048位RSA整数。而没有量子存储器的标准架构需要2000万个量子比特才能完成这项任务。

具体而言，对于10-3的特征物理门错误率，1微秒的处理器周期时间，可在177天内分解2048位RSA整数，假设阈值为0.75%，处理器由13436个物理量子比特制成，存储器可以存储2800万个空间模式和45个时间模式，存储时间为2小时。所需量子比特数减少了3个数量级，代价是运行时间延长了500倍。

图2 使用多模式存储器的计算机架构中处理器的量子比特数和计算n位RSA整数的运行时间

参考文献：

[1]https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.127.140503

[2]https://ieeexplore.ieee.org/document/8490169/

[3]https://quantum-journal.org/papers/q-2021-04-15-433/

—End—

相关阅读：

光子盒将为中国境内的研究机构和企业提供一个免费的垂直招聘信息发布渠道，欢迎有需求的机构或企业直接联系光子盒。（微信：Hordcore）

你可能会错过：